package leetcode100

// TODO 递归 [经典 | 困难] 【-】 二叉树的最近公共祖先
// TODO https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/jsersi-lu-hao-li-jie-by-hyj8/
// TODO 要在纸上 或 ipad 上画出过程

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	// 如果等于 p 或 q, 则要返回它 本身
	if root == q || root == p {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	}
	// 如果它的左右子树都为nil, 则他返回 nil (它不为nil, 也不等于 p 和 q, 所以要返回 nil)
	if left != nil {
		return left
	}
	return right
}
